Many modern data transmission systems use channel coding to reduce bit error rates (BERs) of noisy communication channels. In channel coding a transmitter transmits both data and redundant information generated using the data to a receiver via a channel. The receiver uses the redundant information to correct errors in the data.
Convolutional coding and block coding are the two major forms of channel coding used today. Designed to work on a few bits of data at a time, convolutional coding is particularly well suited for processing continuous data streams. In addition to its use in channel coding, convolutional coding also finds use in optical storage devices, image processing, speech recognition, multiple target tracking, holographic memory systems, predicting microwave propagation loss, and handwriting recognition, for example.
FIG. 1 is a diagram of one embodiment of a convolutional encoder 100 including 4 storage registers 102A–102D connected in series to form a shift register 104, and two EXCLUSIVE-OR gates 106A and 106B. As indicated in FIG. 1, each of the 4 storage registers 102A–102D represents a different one of 4 state elements S0–S3. The 4 state elements S0–S3 define 24=16 unique states of the convolutional encoder 100 defined by the state element grouping “S3S2S1S0.” Taps between various stages of the shift register 104 provide inputs to the EXCLUSIVE-OR gates 106A and 106B. At time interval n (i.e., in stage n), the first register 102A of the shift register 104 receives input data bit D(n). The previous value stored in the first register 102A, D(n−1), is shifted into the second register 102B. Similarly, the value stored in the second register 102B, D(n−2), is shifted into the third register 102C. The value in the third register 102C, D(n−3) shifts into the fourth register 102D and the value in the fourth register 102D, D(n−4) is shifted out of the shift register 104. The EXCLUSIVE-OR gate 106A produces a first output bit G0 where G0=D(n)+D(n−3)+D(n−4), and the EXCLUSIVE-OR gate 106B produces a second output bit G1 where G1=D(n)+D(n−1)+D(n−3)+D(n−4).
As each input data bit can influence output bits over 5 sequential time intervals (stages), the convolutional encoder 100 of FIG. 1 is said to have a constraint length K=5. Two output bits are produced for every input data bit, thus the convolutional encoder 100 of FIG. 1 has a code rate of ½.
Viterbi decoding is a popular technique for decoding convolution codes. The Viterbi decoding algorithm has fixed decoding times and is well suited for hardware implementations. Viterbi decoding, also known as maximum-likelihood decoding, generally involves finding an optimal path through a trellis diagram, then tracing back through the trellis diagram along the optimal path to generate decoded output bits. In general, a trellis diagram includes information regarding each of the states at chronological time intervals (i.e., stages). A common two-dimensional representation of a trellis diagram is an array of nodes having a row for each state and a column for each stage. Arrows or lines between nodes in sequential stages represent transitions or branches between the states.
FIG. 2 is a diagram of a portion 200 of a trellis diagram corresponding to the convolutional encoder 100 of FIG. 1. The trellis diagram may be used to represent the convolutional encoding performed by the encoder 100 and/or the decoding of the convolutional code produced by the encoder 100. The portion 200 of the trellis diagram shown in FIG. 2 includes an array of nodes arranged in 16 rows, one for each of the 16 possible states of the encoder 100, and 2 columns, one for a stage (n−1) and a second for a subsequent stage n. Arrows between the nodes represent transitions or branches between the states. Arrows with solid lines represent transitions occurring when the input data bit D(n) to the encoder 100 of FIG. 1 is a ‘0’, and arrows with dashed lines represent transitions occurring when the input data bit D(n) encoder 100 is a ‘1’.
In FIG. 2, two pairs of encoded input bits (G0, G1), generated using the equations above, are shown above each node in stage (n−1). The first pair of encoded input bits is the output bits produced by the encoder 100 when the input data bit D(n) is a ‘0’, and the second pair of encoded input bits is the output bits produced by the encoder 100 when the input data bit D(n) encoder 100 is a ‘1’.
During Viterbi decoding, a cost metric is used at each stage of the trellis diagram to compute branch costs for each transition or branch. At each state, a branch cost associated with each of two incoming paths are computed and used to select a “survivor” path; the non-surviving path is abandoned. The branch cost associated with a particular transition represents the probability of the transition being correct. For a trellis diagram having a total of M states, at most M paths survive at each stage regardless of the number of stages. The M path costs associated with the M surviving paths are maintained as path metrics, each being a stage-by-stage, cumulative sum of the individual branch costs along the corresponding path. Each path metric represents a probability that the sequence of transitions along the path is correct.
At each stage, path metrics for each new state are calculated using each incoming branch cost plus the previous path cost associated with that branch. The minimum of the two incoming paths is selected as the survivor.
After completing a number of stages greater than the message frame length, a path having the greatest probability of being correct (i.e., having the most favorable metric) is identified by tracing back from node to node through the history of the surviving paths in reverse order. At each stage the surviving path having the greatest probability of being correct (i.e., having the lowest path metric) is selected. For each selected transition, a state transition table for the convolutional encoder 100 of FIG. 1 is used to determine the input data values resulting in the selected transition. The original input data bit sequence can thus be obtained in reverse order.